Search for: All records

Probabilistic Simple Temporal Networks (PSTN) facilitate solving many interesting scheduling problems by characterizing uncertain task durations with unbounded probabilistic distributions. However, most current approaches assess PSTN performance using normal or uniform distributions of temporal uncertainty. This paper explores how well such approaches extend to families of non-symmetric distributions shown to better represent the temporal uncertainty introduced by, e.g., human teammates by building new PSTN benchmarks. We also build probability-aware variations of current approaches that are more reactive to the shape of the underlying distributions. We empirically evaluate the original and modified approaches over well-established PSTN datasets. Our results demonstrate that alignment between the planning model and reality significantly impacts performance. While our ideas for augmenting existing algorithms to better account for human-style uncertainty yield only marginal gains, our results surprisingly demonstrate that existing methods handle positively-skewed temporal uncertainty better. 

Flexibility is generally agreed to be a desirable feature of a Simple Temporal Network (STN). However, exactly what flexibility attempts to measure has varied, making it difficult to objectively evaluate flexibility metrics. Further, past metrics tend to lose information or exhibit other undesirable properties when aggregating the flexibility measures of individual events across an entire STN. Our work is driven by the realization that the solution space of an STN is a convex polyhedron whose geometric properties convey useful information about the STN. These geometric inspirations lead to measures of an STN solution space and also motivate a set of desiderata for general flexibility metrics. We also put forth two new geometrically-inspired flexibility metrics that have some theoretical advantages over existing metrics. Finally, we comprehensively evaluate both new and existing flexibility metrics against our proposed desiderata.